package qjc.l_栈;

import java.util.ArrayDeque;
import java.util.Deque;

public class l5_柱状图中最大的矩形 {
    public int largestRectangleArea(int[] heights) {
        if(heights==null||heights.length==0){
            return 0;
        }
        int n=heights.length;
        int[] newHeights = new int[n+2];
        newHeights[0] = 0;
        newHeights[n+1]=0;
        System.arraycopy(heights, 0, newHeights, 1, n);
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        int maxArea = 0;
        for(int i=1;i<newHeights.length;i++){
            while(newHeights[i]<newHeights[stack.peek()]){
                int height=newHeights[stack.pop()];
                int width = i-stack.peek()-1;
                maxArea = Math.max(maxArea,height*width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}
